/*
day266
2020.5.20
*/
#include<vector>
#include<queue>
#include<iostream> 
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> BSTSequences(TreeNode* root) {
        if(!root) return {{}};
        
        queue<TreeNode*> que;
        vector<int> path;
        path.push_back(root->val);
        core(root,que,path);
        return ans;
    }


    void core(TreeNode* root,queue<TreeNode*> que,vector<int> &path){
        if(!root) return;
        if(root->left) que.push(root->left);
        if(root->right) que.push(root->right);
        if(que.empty()){
            ans.push_back(path);
            return;
        }
        int n=que.size();
        while(n--){
            TreeNode* cur=que.front();que.pop();
            path.push_back(cur->val);
            core(cur,que,path);
            que.push(cur);
            path.pop_back();
        }
    }
};




class Solution2 {
public:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        vector<vector<int>> ans;
    	if(!root)
    	{
    		return {{}};
		}
        queue<TreeNode *> que;
        vector<int> path;
		que.push(root);
		
		core(que,path,ans);
    	return ans;
    }


    void core(queue<TreeNode*> &que,vector<int> &path,vector<vector<int>> &ans)
	{
        int size=que.size();
        if(size==0)
        {
        	ans.push_back(path);
        	return ;
		}
		
		for(int i=0;i<size;++i)
		{
			TreeNode *cur_root=que.front();
			path.push_back(cur_root->val);
			que.pop();
			
			int child=0;
			if(cur_root->left)
			{
				child++;
				que.push(cur_root->left);
			}
			if(cur_root->right)
			{
				child++;
				que.push(cur_root->right);
			}
			
			core(que,path,ans);
			
			for(int j=0;j<child;j++)
			{
				que.pop();
			}
			path.pop_back();
			que.push(cur_root);	
		}
    }
};


class Solution3 {
public:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        if (!root) return {{}};
        deque<TreeNode*> q;
        q.push_back(root);
        vector<int> buf;
        vector<vector<int> > ans;
        Inner(q, buf, ans);
        return ans;
    }
    void Inner(deque<TreeNode*> &q, vector<int> &buf, vector<vector<int> > &ans) {
        if (q.empty()) {
            ans.push_back(buf);
            return;
        }
        int size = q.size();
        while (size--) {
            TreeNode *r = q.front(); q.pop_front();
            buf.push_back(r->val);
            int children = 0;
            if (r->left) {
                ++children;
                q.push_back(r->left);
            }
            if (r->right) {
                ++children;
                q.push_back(r->right);
            }
            Inner(q, buf, ans);
            while (children--) {
                q.pop_back();
            }
            q.push_back(r);
            buf.pop_back();
        }
    }
};



int main()
{
	return 0;
}


